package ahjava.p12exercises.algorithm;
import java.util.Arrays;
public class T001海盗_最优装载 {
	// 贪心算法：做出当前最好的选择，期望通过局部最优解，得到全局最优解
	// 贪心的本质：只顾眼前的苟且
	// 贪心的效果：能得到许多问题的最优解，或近似最优解
	// 注意事项：有可能只是近似最优解，所以要“选择，并承担后果”
	// 贪心策略：买苹果，有人爱大，有人喜红。拿大取红，皆为策略。冒泡排序，用的贪心算法
	// 贪亦有道：并非所有问题都可以贪心解之。可以贪心的问题有两个特征：
	// 1.贪心选择性质——整体最优解，可以由局部最优解得到，不依赖未作出的选择
	// 2.最优子结构性质——问题的最优解包含其子问题的最优解
	// 加勒比海盗——最优装载问题
	// 17世纪，北美东南，海盗猖獗，攻击过往商人，甚至英国皇家舰队。
	// 海盗截获货船，每件商品重量为Wi，海盗船载重为C，问海盗如何装载数量最多的宝贝
	// 算法：将商品重量从小到大排序，依次装入，直到上限
	static int[] W = { 4, 10, 7, 11, 3, 5, 14, 2 };
	static int C = 30;
	public static void main(String[] args) {
		Arrays.sort(W);
		System.out.println(Arrays.toString(W));
		int count = 0;// 一共装走n件
		for (int i : W) {
			if (C <= i) {
				break;
			} else {
				System.out.print(i + " ");
				C = C - i;
				count++;
			}
		}
		System.out.println("一共装走：" + count + "件");
	}
}
